5.3.2. Прямая и обратная цепочки рассуждений

На глобальном уровне управления последовательностью применения правил можно выделить две стратегии поведения — применять правила в прямом и обратном порядке. Прямой порядок означает, что цепь рассуждений строится, отталкиваясь от данных (условий, о которых известно, что они удовлетворяются), к гипотезам (состоянию проблемы, вытекающему из этих условий). Обратная цепочка означает, что рассуждения строятся, отталкиваясь от заданной цели (гипотезы, представляющие целевое состояние системы) к условиям, при которых возможно достижение этой цели. Здесь явно чувствуется аналогия с прямой и обратной стратегиями доказательства теорем (см. об этом в главе 8).

CLIPS представляет собой систему, в которой строится прямая цепочка рассуждений, а порождающие правила в системе MYCIN используются в большинстве случаев для построения обратной цепочки рассуждений, как было показано в главе 3. В CLIPS всегда сопоставляются состояние рабочей памяти и левые части правил, а затем выполняются действия, предусмотренные правой частью выбранного правила. А в MYCIN ведущей в рассуждениях является правая часть правила. Если мы задались целью установить природу некоторого микроорганизма, то отбираются все правила, в правой части которых дается соответствующее заключение, и затем анализируется, предпосылки какого из них удовлетворяются текущими данными.

Проще всего представить отличие между прямой и обратной цепочками рассуждений в терминах грамматических правил, аналогичных представленным в разделе 5.1. Как было показано, набор правил

(Р1) $ -> а$а

(Р2) $ -> b$b

(РЗ) $ -> с$с

можно использовать двумя способами.

Во-первых, их можно использовать для формирования палиндромов. Если задаться некоторым начальным символом из имеющегося алфавита, то любая последовательность применения правил приведет к формированию палиндрома. Так, применение правил Р1, Р1, РЗ, Р2, Р3 к исходному символу с приведет к формированию строк

аса, aacaa, caacaac, bcaacaacb, cbcaacaacbc.

Это пример прямой цепочки, поскольку с и каждая последующая сформированная строка сопоставляются с левой частью правила, а затем означивается правая часть правила.

Во-вторых, можно использовать этот же набор правил не для формирования, а для распознавания палиндромов. Мы уже видели ранее, что, задавшись некоторой строкой, например ЬасаЬ, можно проследить, в какой последовательности применялись правила при построении этой строки. Строка bасаb соответствует правой части правила Р2; можно сказать, что правая часть правила Р2 "допускает" строку bacab. Означенная левая часть правила Р2 — это строка аса, которая соответствует правой части правила PI, a означенная левая часть этого правила — аксиома с. Таким образом, процесс распознавания успешно завершился — мы доказали, что bacab представляет собой палиндром. Описанный процесс распознавания — это пример применения обратной цепочки рассуждений. Начальная строка bacab и каждая очередная подстрока анализируются на соответствие с правыми частями имеющихся правил, а результатом является означивание левой части выбранного правила. Если в качестве исходной мы зададимся строкой acbcb, то для нее не удастся найти в имеющемся наборе правил такое, правая часть которого "допускала" бы эту строку, а значит, исходная строка не может быть палиндромом.

В литературе по теории доказательства теорем прямая цепочка рассуждений, как правило, ассоциируется с "восходящим" процессом, т.е. рассуждениями от фактов к целям, а обратная цепочка — с "нисходящим" процессом, рассуждением от целей к фактам. Но, строго говоря, в отношении продукционных систем эти термины не являются синонимами. Например, вполне возможно реализовать нисходящий процесс в продукционной системе с прямой цепочкой рассуждений, если должным образом настроить локальный режим управления, например задать явное указание целей.

В листинге 5.4 показана простая программа построения башни из блоков. Эта программа переключается между двумя задачами: выбором очередного блока и установкой блока в башню.

В разделе шаблонов блоки представлены объектами, обладающими такими свойствами, как цвет, размер и положение. Если положение блока не определено, предполагается, что он находится в куче блоков (heap), еще не уложенных в башню. Шаблон on предоставляет в наше распоряжение средство, позволяющее описать размещение блоков одного (upper) на другом (lower). Информацию о текущей фазе решения проблемы (поиск или установка) несет шаблон goal.

Листинг 5.4. Набор правил для построения башни из блоков

;; СТРАТЕГИЯ РАЗРЕШЕНИЯ КОНФЛИКТОВ

(declare (strategy mea))

;; Шаблоны

;; Объект block характеризуется цветом, размером и положением,

(deftemplate block

(field color (type SYMBOL))

(field size (type INTEGER))

(field place (type SYMBOL)) )

;; Вектор 'on' указывает, что блок <upper>

;; находится на блоке <lower>. (deftemplate on

(field upper (type SYMBOL»

(field lower (type SYMBOL))

(field place (type SYMBOL) (default heap)] )

;; Текущая цель (goal) может быть либо 'найти' (find),

;; либо 'уложить' (build), (deftemplate goal

(field task (type SYMBOL)) )

;; ИНИЦИАЛИЗАЦИЯ

;; Имеются три блока разных цветов и размеров.

;; Предполагается, что они находятся в куче.

(deffacts the-facts

(block (color red) (size 10))

(block(color yellow) (size 20))

(block (color blue) (size 30))

)

;; ПРАВИЛА

;; Задать первую цель: найти первый блок,

(defrule begin

(initial-fact) =>

(assert (goal (task find))) )

;; Взять самый большой блок в куче (heap),

(defrule pick-up

?my-goal <- (goal (task find))

?my-block <- (block (size ?S1) (place heap))

(not (block (color ?C2) (size ?S2&:(>-?S2 ?S1))

(place heap))) =>

(modify ?my-block (place hand))

(modify ?my-goal (task build)) )

;; Установить первый блок в основание башни (tower).

;; Этот блок не имеет под собой никакого другого,

(defrule place-first

?my-goal <- (goal (task build))

?my-block <- (block (place hand))

(not (block (place tower)))

=>

(modify ?my-block (place tower))

(modify ?my-goal (task find)) )

;; Установить последующие блоки на тот,

;; что лежит в основании башни,

(defrule put-down

?my-goal <- (goal (task build))

?my-block <- (block (color ?C0)

(place hand))

(block (color ?C1) (place tower)))

(not (on (upper ?C2) (lower ?C1)

(place tower)))

=>

(modify ?my-block (place tower))

(assert (on (upper ?CO) (lower ?C1)

(place tower)))

(modify ?my-goal (task find)) )

;; Если в куче больше нет блоков, прекратить процесс,

(defrule stop

?my-goal <- (goal (task find))

(not (block (place heap)))

=>

(retract ?my-goal) )

Обратите внимание на то, что порядок перечисления правил в программе не имеет значения. В программе управления роботом, представленной в листинге 5.3, правило прекращения выполнения стояло в списке первым, а в этой программе оно стоит в самом конце списка. Трассировку выполнения приведенной программы и некоторые комментарии вы найдете во врезке 5.4.

5.4. Трассировка программы строительства башни

При запуске программы в режиме трассировки будет сформирована следующая карта трассировки.

CLIPS> (reset)

==> f-0 (initial-fact)

==> f-1 (block (color red) (size 10) (place heap))

==>f-2 (block (color yellow) (size 20) (place heap))

==> f-3 (block (color blue) (size 30) (place heap))

CLIPS> (run)

TIRE 1 begin: f-0

==> f-4 (goal (task find))

FIRE 2 pick-up: f-4, f-3,

<== f-3 (block (color blue) (size 30) (place heap))

==> f-5 (block (color blue) (size 30) (place hand))

<== f-4 (goal (task find))

==> f-6 (goal (task build))

FIRE 3 place-first: f-6, f-5,

<== f-5 (block (color blue) (size 30) (place hand))

==> f-7 (block (color blue) (size 30) (place tower))

<== f-6 (goal (task build))

==> f-8 (goal (task find))

FIRE 4 pick-up: f-8, f-2,

<== f-2 (block (color yellow) (size 20) (place heap))

==> f-5 (block (color yellow) (size 20) (place hand))

<== f-8 (goal (task find))

==> f-10 (goal (task build))

FIRE 5 put-down: f-10, f-9, f-7,

<== f-9 (block (color yellow) (size 20) (place hand))

==>. f-11 (block (color yellow) (size 20) (place tower))

==> f-12 (on (upper yellow) (lower blue) (place tower))

<== f-10 (goal (task build))

==> f-13 (goal (task find))

FIRE 6 pick-up: f-13, f-1,

<== f-1 (block (color red) (size 10) (place heap))

==> f-5 (block (color red) (size 10) (place hand))

<== f-13 (goal (task find))

==> f-15 (goal (task build))

FIRE 7 put-down: f-15, f-14, f-11,

<== f-14 (block (color red) (size 10) (place hand))

==> f-16 (block (color red) (size 10) (place tower))

==> f-17 (on (upper red) (lower yellow) (place tower))

<== f-15 (goal (task build))

==> f-18 (goal (task find))

FIRE 8 stop: f-18,

<== f-18 (goal (task find))

CLIPS> (reset)

<== f-0 (initial-fact)

<== f-7 (block (color blue) (size 30) (place tower))

<== f-11 (block (color yellow) (size 20) (place tower))

<== f-12 (on (upper yellow) (lower blue) (place tower))

<== f-16 (block (color red) (size 10) (place tower))

<== f-17 (on (upper red) (lower yellow) (place tower))

Обратите внимание на манипулирование лексемой цели в ходе выполнения программы. Конечное состояние представлено при очистке рабочей памяти. Блоки в башне расположились в таком порядке: красный (red) — самый верхний, он стоит на желтом (yellow), который стоит на синем (blue).

Особенность этого примера в том, что в программе реализована нисходящая стратегия рассуждений, хотя правила предполагают использование прямой цепочки анализа данных, т.е. "работают" в направлении снизу вверх. Этот эффект достигается манипулированием лексемами цели. В данном случае выражение (initial-fact) формулирует цель верхнего уровня — построить башню. Эта цель имеет две подцели — поиск блока и установка блока в башню, которые представлены лексемами

(goal (task find)

и

(goal (task build)).

Когда оказывается, что в куче больше нет блоков, главная цель достигнута. Мы делаем это в определенной степени неформально, используя (initial-fact) для упрощения программного кода, но принцип, тем не менее, соблюдается.

Иногда необходимо провести четкую границу между направленностью цепочки и направленностью действительных рассуждений. Эти две операции представляют разные уровни анализа. Очевидно, что цепочка является реализацией рассуждений, а не наоборот, но стратегия рассуждений управляет процессом построения цепочки, что в данном случае выполняется манипулированием лексемами цели. В главе 14 будет продемонстрирован гораздо более сложный пример использования этого метода в системе R1/XCON.

Это разделение высвечивает проблему, с которой очень часто приходится сталкиваться при обсуждении функционирования программ искусственного интеллекта. Большинство сложных систем, независимо от того, являются ли они программными системами, или физическими устройствами, или комбинацией тех и других, могут быть описаны на разных уровнях [Newell, 1982]. В соответствии с терминологией Ньюэлла, построение цепочки — это свойство символического уровня, где нас интересуют только левые и правые части правил, а рассуждение— это нечто, возникающее на уровне знаний, где можно провести разделение между фактами и задачами.

Ранее уже утверждалось, что большинство порождающих правил, представляющих реальный интерес с точки зрения приложений искусственного интеллекта, являются недетерминированными. При построении прямой цепочки рассуждений может оказаться, что текущие данные удовлетворяют предпосылки не одного правила, а нескольких. При построении обратной цепочки также зачастую оказывается, что одна и та же цель достигается при выполнении не единственного правила, а нескольких. Поэтому понятно, какая важная роль отводится механизму управления правилами в функционировании продукционной системы.

В главе 3 мы рассказывали о представлении пространства поиска, связанного с набором порождающих правил, с помощью И/ИЛИ-дерева. Узлы такого дерева соответствуют состояниям рабочей памяти, а дуги — правилам, которые при этом возможно применить. Древовидная схема очень хорошо согласуется с методикой обратной цепочки рассуждений, если считать, что корень дерева соответствует целевому состоянию, промежуточные узлы — подцелям, а терминальные узлы (листья) — данным.

В И/ИЛИ-дереве корень представляет исходное состояние проблемы, а листья — возможные варианты ее решения. Нетерминальные узлы могут быть двух видов: И-узлы и ИЛИ-узлы. И-узлы соответствуют применению нескольких правил, которые в совокупности формируют цель как объединение нескольких подцелей, а ИЛИ-узлы соответствуют наличию альтернативы при выборе возможных правил. Таким образом, используя терминологию главы 2, можно говорить о том, что возможные варианты применения правил формируют пространство поиска и определяют его структуру.

Программирование, основанное на правилах (логическое программирование), не снимает с повестки дня проблему комбинаторного взрыва, поскольку для любой проблемы И/ИЛИ-дерево может ветвиться по экспоненциальному закону. Но на практике стратегия разрешения конфликтов, реализованная в интерпретаторах правил, позволяет надеяться на отыскание разумного решения.